package 力扣._00周赛._146双周赛.问题3;

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.TreeSet;

class Solution2 {
    public boolean checkValidCuts(int n, int[][] rectangles) {

        HashSet<Integer> xBoundaries = new HashSet<>();
        HashSet<Integer> yBoundaries = new HashSet<>();

        // rectangles按照x坐标排序
        Arrays.sort(rectangles, Comparator.comparingInt(a -> a[2]));
        for (int i =0;i< rectangles.length;i++){
            int[] rectangle = rectangles[i];
            int x1 = rectangle[0];
            int x2 = rectangle[2];
            boolean flag = false;
            for (int j = i-1; j >=0 ; j--) {
                if((x1 > rectangles[j][0] && x1 < rectangles[j][2])||
                        (rectangles[j][0]>x1 && rectangles[j][0]<x2)||
                        (rectangles[j][2]>x1 && rectangles[j][2]<x2)
                ){
                    flag = true;
                    xBoundaries.remove(rectangles[j][0]);
                    xBoundaries.remove(rectangles[j][2]);
                }
                if(x1>=rectangles[j][2])
                    break;
            }
            if(!flag){
                xBoundaries.add(x1);
                xBoundaries.add(x2);
            }
        }
        System.out.println(xBoundaries);
        if(xBoundaries.size() > 4){
            return true;
        }

        // rectangles按照y坐标排序
        Arrays.sort(rectangles, Comparator.comparingInt(a -> a[3]));
        for (int i =0;i< rectangles.length;i++){
            int[] rectangle = rectangles[i];
            int y1 = rectangle[1];
            int y2 = rectangle[3];
            boolean flag = false;
            for (int j = i-1; j >=0 ; j--) {
                if((y1 > rectangles[j][1] && y1 < rectangles[j][3])
                        ||(rectangles[j][1]>y1 && rectangles[j][1]<y2)
                        ||(rectangles[j][3]>y1 && rectangles[j][3]<y2)){
                    flag = true;
                    yBoundaries.remove(rectangles[j][1]);
                    yBoundaries.remove(rectangles[j][3]);
                }
                if(y1>=rectangles[j][3])
                    break;
            }
            if(!flag){
                yBoundaries.add(y1);
                yBoundaries.add(y2);
            }
        }
        System.out.println(yBoundaries);
        return yBoundaries.size() > 4;
    }


    public static void main(String[] args) {
        // 5
        //[[1,0,5,2],[0,2,2,4],[3,2,5,3],[0,4,4,5]]©leetcode
        int n = 5;
        int[][] rectangles = new int[][]{{1, 0, 5, 2}, {0, 2, 2, 4}, {3, 2, 5, 3}, {0, 4, 4, 5}};
//        System.out.println(new Solution().checkValidCuts(n, rectangles));

        // 4
        // [[0,2,2,4],[1,0,3,2],[2,2,3,4],[3,0,4,2],[3,2,4,4]]©leetcode
//        int n = 4;
//        int[][] rectangles = new int[][]{{0,2,2,4},{1,0,3,2},{2,2,3,4},{3,0,4,2},{3,2,4,4}};

        // 3
        // [[0,0,1,3],[1,0,2,3],[2,0,3,3]]
//        int n = 3;
//        int[][] rectangles = new int[][]{{0,0,1,3},{1,0,2,3},{2,0,3,3}};

        // 3
        // [[0,0,1,3],[1,0,2,2],[2,0,3,2],[1,2,3,3]]
//        int n = 3;
//        int[][] rectangles = new int[][]{{0,0,1,3},{1,0,2,2},{2,0,3,2},{1,2,3,3}};
        System.out.println(new Solution2().checkValidCuts(n, rectangles));
    }
}